%Przegląd algorytmów stosowanych do rozwiązywania problemu opisywanych
%we współczesnej literaturze

% TODO - reorganizacja + jakies linki do opisów algorytmów

\section{Algorytmy}

Opierając się na znalezionej literaturze prezentujemy krótki przegląd algorytmów wykorzystywanych do rozwiązywania problemu SameGame.

\subsection{Przegląd algorytmów}

W publikacji naukowej ''Solving SameGame and its Chessboard Variant'' \cite{samegame-solving} opisano kilka sposobów rozwiązania problemu, oraz przeprowadzono szereg symulacji pozwalających na ich porównanie.

\subsubsection{Brute force}

Ze względu na złożoność problemu, uwzględniając rozmiar planszy do gry, oraz większą ilość kolorów, metoda brute force nie przynosi rozwiązania w zadowalającym czasie. Spowodowane jest to tym, że wymagają one bardzo dobrej estymacji wartości podjęcia danego kroku, co jest praktycznie niemożliwe. Różne usprawnienia algorytmu nie przyniosły spodziewanych rezultatów. Ponadto usprawnienia te mogły prowadzić do błędnych rozwiązań, nie pozwalających na ukończenie gry. 

\subsubsection{Beam Search}

Kolejnym rozważanym algorytmem pojawiającym się w literaturze jest Beam-Search. Jest to heurystyczny algorytm polegający na optymalizacji algorytmu Best-First. Algorytm polega na przeszukiwaniu grafu przewidując najbardziej obiecujące kolejne posunięcia. Algorytm nie przeszukuje całej puli możliwości a jedynie pewien zakres najlepszych wyborów co też przyspiesza działanie samego algorytmu.

\subsubsection{Algorytm bankiera}

Algorytm Bankiera przydziela pewien budżet dla każdego wierzchołka grafu przeszukiwania. Zagłębianie się w kolejne kroki rozwiązania jest możliwe tylko wtedy gdy budżet nie został jeszcze w całości wydany. W przeciwnym wypadku przeszukiwanie staje się zachłanne.

W grze SameGame budżet mógłby być wyliczany z liczby klocków danego koloru, lub wielkości podgrup jakie tworzą poszczególne klocki danego koloru. 

\subsubsection{Przeszukiwanie Monte Carlo}

Przeszukiwanie Monte Carlo jest pewnym wariantem algorytmu Best-First przeszukującego graf. Przeszukiwanie to nie polega jednak na wyliczaniu wartości funkcji estymacyjnej, a na przeprowadzeniu pewnej liczby symulacji dla danego wierzchołka. Wartość jakości rozwiązania polega na aktualnym stanie planszy. 

Zaproponowane rozwiązanie przez autorów publikacji optymalizuje algorytm Monte Carlo. Wariant ten nazwano Monte Carlo z wybieraniem ruletkowym. Optymalizacja polega na próbie utworzenia jak największych bloków dla różnych kolorów. 

\subsubsection{Algorytm SP-MCTS}

Obecnie jedną z najpopularniejszych metod rozwiązywania problemów typu SameGame jest Single-Player Monte Carlo Tree Search(SP-MCTS).

Monte-Carlo Tree Search (MCTS) to algorytm wyszukiwania. W dzisiejszych czasach jest używany do wyznaczania najlepszych ruchów w takich grach jak Go. Metoda świetnie znajduje zastosowanie w grach, gdzie trudno jest wyznaczyć funkcję oceny. Przykłady : Go, SameGame. 

SP-MCTS może być użyta na 2 sposoby:
\begin{itemize}
	\item konstrukcja drzewa dla całej gry
	\item konstrukcja drzewa dla każdego kroku
\end{itemize}

Algorytm z konstrukcją drzewa dla każdego kroku daje lepsze wyniki. Każdemu węzłowi odpowiada pozycja na planszy. Każdy węzeł przechowuje swój licznik odwiedzin i wartość. MCTS składa się z czterech faz: selection, simulation, expansion i backpropagation. Fazy są powtarzane póki nie skończy się czas. Krok zagrania – syn korzenia o największej wartości. Fazy:
\begin{itemize}
	\item Selection – Faza definiująca sposób poruszania się w drzewie, od korzenia do liścia, a dokładniej wybieranie kolejnego dziecka danego węzła. Algorytm musi być zbalansowany pomiędzy wykorzystaniem dobrych już znanych ruchów a znalezieniem nowych, być może lepszych.
	\item Simulation – Przeprowadzamy określoną symulację dla całego drzewa zaczynając od korzenia (początek gry). Wykonujemy losowe ruchy aż dojdziemy do końca gry to jest ostatniego liścia w drzewie. Kolejne ruchy wybierane są przez pseudo-losowy generator oparty na algorytmie heurystycznym. 
	Przykładową strategią dokonywania ruchów jest tworzenie dużych grup określonego koloru. Wybierany jest dany kolor i budujemy grupę aż w kolejnych liściach zabraknie danego koloru. Wybieramy kolejny kolor i znowu powtarzamy algorytm aż do końca danej gry.
	W jednym kroku symulacji może wystąpić kilka strategii działania.
	\item Expansion – Kiedy następuje koniec gry, strategia zawarta w kroku Expansion decyduje, czy zapisać ścieżkę lub dane węzły do pamięci. 
	Jedną ze strategii zapisu jest rozszerzanie poszukiwań o węzły obok najlepszych ścieżek, polega to na szukaniu rozwiązań nie wzdłuż, czyli od korzenia do liści, a wszerz, czyli modernizowaniu najlepszych ścieżek modyfikując elementy w ścieżce.
	\item Backpropagation – etap w którym są propagowane wyniki przeszukiwań wstecz od liści, zapisanych w poprzednich etapach lub znajdujących się na ścieżkach najlepszych rozwiązań, do korzenia. 
	Jedną ze strategii tego etapu jest aktualizowanie wartości danego węzła w zależności od poszczególnych rozwiązań,czyli szukanie najlepszego rozwiązania z dwóch nachodzących na siebie ścieżek.
\end{itemize}

W każdym etapie można zastosować bardzo wiele strategii, niektóre zostały opisane w publikacji
''Single-Player Monte-Carlo Tree Search'' \cite{monte-carlo}


